H-Termination proof of /home/matraf/haskell/eval_FullyBlown

YES 0.962 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/List.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:

↳ HASKELL

  ↳ IFR

mainModule List

((delete :: Char -> [Char] -> [Char]) :: Char -> [Char] -> [Char])

module List where

import qualified Maybe
import qualified Prelude

delete :: Eq a => a -> [a] -> [a]

delete

deleteBy (==)

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

deleteBy	_ _ []	=	[]
deleteBy	eq x (y : ys)	=	if x `eq` y then ys else y : deleteBy eq x ys

module Maybe where

import qualified List
import qualified Prelude

If Reductions:
The following If expression

if eq x y then ys else y : deleteBy eq x ys

is transformed to

deleteBy0 ys y eq x True = ys

deleteBy0 ys y eq x False = y : deleteBy eq x ys

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

mainModule List

((delete :: Char -> [Char] -> [Char]) :: Char -> [Char] -> [Char])

module List where

import qualified Maybe
import qualified Prelude

delete :: Eq a => a -> [a] -> [a]

delete

deleteBy (==)

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

deleteBy	_ _ []	=	[]
deleteBy	eq x (y : ys)	=	deleteBy0 ys y eq x (x `eq` y)

deleteBy0	ys y eq x True	=	ys
deleteBy0	ys y eq x False	=	y : deleteBy eq x ys

module Maybe where

import qualified List
import qualified Prelude

Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

        ↳ HASKELL

          ↳ COR

mainModule List

((delete :: Char -> [Char] -> [Char]) :: Char -> [Char] -> [Char])

module List where

import qualified Maybe
import qualified Prelude

delete :: Eq a => a -> [a] -> [a]

delete

deleteBy (==)

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

deleteBy	vw vx []	=	[]
deleteBy	eq x (y : ys)	=	deleteBy0 ys y eq x (x `eq` y)

deleteBy0	ys y eq x True	=	ys
deleteBy0	ys y eq x False	=	y : deleteBy eq x ys

module Maybe where

import qualified List
import qualified Prelude

Cond Reductions:
The following Function with conditions

undefined

| False

= undefined

is transformed to

undefined = undefined1

undefined0 True = undefined

undefined1 = undefined0 False

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

        ↳ HASKELL

          ↳ COR

            ↳ HASKELL

              ↳ Narrow

mainModule List

(delete :: Char -> [Char] -> [Char])

module List where

import qualified Maybe
import qualified Prelude

delete :: Eq a => a -> [a] -> [a]

delete

deleteBy (==)

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

deleteBy	vw vx []	=	[]
deleteBy	eq x (y : ys)	=	deleteBy0 ys y eq x (x `eq` y)

deleteBy0	ys y eq x True	=	ys
deleteBy0	ys y eq x False	=	y : deleteBy eq x ys

module Maybe where

import qualified List
import qualified Prelude

Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="delete",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="delete wu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
4[label="delete wu3 wu4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
5[label="deleteBy (==) wu3 wu4",fontsize=16,color="burlywood",shape="box"];186[label="wu4/wu40 : wu41",fontsize=10,color="white",style="solid",shape="box"];5 -> 186[label="",style="solid", color="burlywood", weight=9];
186 -> 6[label="",style="solid", color="burlywood", weight=3];
187[label="wu4/[]",fontsize=10,color="white",style="solid",shape="box"];5 -> 187[label="",style="solid", color="burlywood", weight=9];
187 -> 7[label="",style="solid", color="burlywood", weight=3];
6[label="deleteBy (==) wu3 (wu40 : wu41)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3];
7[label="deleteBy (==) wu3 []",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3];
8[label="deleteBy0 wu41 wu40 (==) wu3 ((==) wu3 wu40)",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
9[label="[]",fontsize=16,color="green",shape="box"];10[label="deleteBy0 wu41 wu40 primEqChar wu3 (primEqChar wu3 wu40)",fontsize=16,color="burlywood",shape="triangle"];188[label="wu3/Char wu30",fontsize=10,color="white",style="solid",shape="box"];10 -> 188[label="",style="solid", color="burlywood", weight=9];
188 -> 11[label="",style="solid", color="burlywood", weight=3];
11[label="deleteBy0 wu41 wu40 primEqChar (Char wu30) (primEqChar (Char wu30) wu40)",fontsize=16,color="burlywood",shape="box"];189[label="wu40/Char wu400",fontsize=10,color="white",style="solid",shape="box"];11 -> 189[label="",style="solid", color="burlywood", weight=9];
189 -> 12[label="",style="solid", color="burlywood", weight=3];
12[label="deleteBy0 wu41 (Char wu400) primEqChar (Char wu30) (primEqChar (Char wu30) (Char wu400))",fontsize=16,color="black",shape="box"];12 -> 13[label="",style="solid", color="black", weight=3];
13[label="deleteBy0 wu41 (Char wu400) primEqChar (Char wu30) (primEqNat wu30 wu400)",fontsize=16,color="burlywood",shape="box"];190[label="wu30/Succ wu300",fontsize=10,color="white",style="solid",shape="box"];13 -> 190[label="",style="solid", color="burlywood", weight=9];
190 -> 14[label="",style="solid", color="burlywood", weight=3];
191[label="wu30/Zero",fontsize=10,color="white",style="solid",shape="box"];13 -> 191[label="",style="solid", color="burlywood", weight=9];
191 -> 15[label="",style="solid", color="burlywood", weight=3];
14[label="deleteBy0 wu41 (Char wu400) primEqChar (Char (Succ wu300)) (primEqNat (Succ wu300) wu400)",fontsize=16,color="burlywood",shape="box"];192[label="wu400/Succ wu4000",fontsize=10,color="white",style="solid",shape="box"];14 -> 192[label="",style="solid", color="burlywood", weight=9];
192 -> 16[label="",style="solid", color="burlywood", weight=3];
193[label="wu400/Zero",fontsize=10,color="white",style="solid",shape="box"];14 -> 193[label="",style="solid", color="burlywood", weight=9];
193 -> 17[label="",style="solid", color="burlywood", weight=3];
15[label="deleteBy0 wu41 (Char wu400) primEqChar (Char Zero) (primEqNat Zero wu400)",fontsize=16,color="burlywood",shape="box"];194[label="wu400/Succ wu4000",fontsize=10,color="white",style="solid",shape="box"];15 -> 194[label="",style="solid", color="burlywood", weight=9];
194 -> 18[label="",style="solid", color="burlywood", weight=3];
195[label="wu400/Zero",fontsize=10,color="white",style="solid",shape="box"];15 -> 195[label="",style="solid", color="burlywood", weight=9];
195 -> 19[label="",style="solid", color="burlywood", weight=3];
16[label="deleteBy0 wu41 (Char (Succ wu4000)) primEqChar (Char (Succ wu300)) (primEqNat (Succ wu300) (Succ wu4000))",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3];
17[label="deleteBy0 wu41 (Char Zero) primEqChar (Char (Succ wu300)) (primEqNat (Succ wu300) Zero)",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3];
18[label="deleteBy0 wu41 (Char (Succ wu4000)) primEqChar (Char Zero) (primEqNat Zero (Succ wu4000))",fontsize=16,color="black",shape="box"];18 -> 22[label="",style="solid", color="black", weight=3];
19[label="deleteBy0 wu41 (Char Zero) primEqChar (Char Zero) (primEqNat Zero Zero)",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3];
20 -> 133[label="",style="dashed", color="red", weight=0];
20[label="deleteBy0 wu41 (Char (Succ wu4000)) primEqChar (Char (Succ wu300)) (primEqNat wu300 wu4000)",fontsize=16,color="magenta"];20 -> 134[label="",style="dashed", color="magenta", weight=3];
20 -> 135[label="",style="dashed", color="magenta", weight=3];
20 -> 136[label="",style="dashed", color="magenta", weight=3];
20 -> 137[label="",style="dashed", color="magenta", weight=3];
20 -> 138[label="",style="dashed", color="magenta", weight=3];
21[label="deleteBy0 wu41 (Char Zero) primEqChar (Char (Succ wu300)) False",fontsize=16,color="black",shape="box"];21 -> 26[label="",style="solid", color="black", weight=3];
22[label="deleteBy0 wu41 (Char (Succ wu4000)) primEqChar (Char Zero) False",fontsize=16,color="black",shape="box"];22 -> 27[label="",style="solid", color="black", weight=3];
23[label="deleteBy0 wu41 (Char Zero) primEqChar (Char Zero) True",fontsize=16,color="black",shape="box"];23 -> 28[label="",style="solid", color="black", weight=3];
134[label="wu4000",fontsize=16,color="green",shape="box"];135[label="wu4000",fontsize=16,color="green",shape="box"];136[label="wu300",fontsize=16,color="green",shape="box"];137[label="wu300",fontsize=16,color="green",shape="box"];138[label="wu41",fontsize=16,color="green",shape="box"];133[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat wu20 wu21)",fontsize=16,color="burlywood",shape="triangle"];197[label="wu20/Succ wu200",fontsize=10,color="white",style="solid",shape="box"];133 -> 197[label="",style="solid", color="burlywood", weight=9];
197 -> 169[label="",style="solid", color="burlywood", weight=3];
198[label="wu20/Zero",fontsize=10,color="white",style="solid",shape="box"];133 -> 198[label="",style="solid", color="burlywood", weight=9];
198 -> 170[label="",style="solid", color="burlywood", weight=3];
26[label="Char Zero : deleteBy primEqChar (Char (Succ wu300)) wu41",fontsize=16,color="green",shape="box"];26 -> 33[label="",style="dashed", color="green", weight=3];
27[label="Char (Succ wu4000) : deleteBy primEqChar (Char Zero) wu41",fontsize=16,color="green",shape="box"];27 -> 34[label="",style="dashed", color="green", weight=3];
28[label="wu41",fontsize=16,color="green",shape="box"];169[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat (Succ wu200) wu21)",fontsize=16,color="burlywood",shape="box"];199[label="wu21/Succ wu210",fontsize=10,color="white",style="solid",shape="box"];169 -> 199[label="",style="solid", color="burlywood", weight=9];
199 -> 171[label="",style="solid", color="burlywood", weight=3];
200[label="wu21/Zero",fontsize=10,color="white",style="solid",shape="box"];169 -> 200[label="",style="solid", color="burlywood", weight=9];
200 -> 172[label="",style="solid", color="burlywood", weight=3];
170[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat Zero wu21)",fontsize=16,color="burlywood",shape="box"];201[label="wu21/Succ wu210",fontsize=10,color="white",style="solid",shape="box"];170 -> 201[label="",style="solid", color="burlywood", weight=9];
201 -> 173[label="",style="solid", color="burlywood", weight=3];
202[label="wu21/Zero",fontsize=10,color="white",style="solid",shape="box"];170 -> 202[label="",style="solid", color="burlywood", weight=9];
202 -> 174[label="",style="solid", color="burlywood", weight=3];
33[label="deleteBy primEqChar (Char (Succ wu300)) wu41",fontsize=16,color="burlywood",shape="triangle"];203[label="wu41/wu410 : wu411",fontsize=10,color="white",style="solid",shape="box"];33 -> 203[label="",style="solid", color="burlywood", weight=9];
203 -> 39[label="",style="solid", color="burlywood", weight=3];
204[label="wu41/[]",fontsize=10,color="white",style="solid",shape="box"];33 -> 204[label="",style="solid", color="burlywood", weight=9];
204 -> 40[label="",style="solid", color="burlywood", weight=3];
34[label="deleteBy primEqChar (Char Zero) wu41",fontsize=16,color="burlywood",shape="box"];205[label="wu41/wu410 : wu411",fontsize=10,color="white",style="solid",shape="box"];34 -> 205[label="",style="solid", color="burlywood", weight=9];
205 -> 41[label="",style="solid", color="burlywood", weight=3];
206[label="wu41/[]",fontsize=10,color="white",style="solid",shape="box"];34 -> 206[label="",style="solid", color="burlywood", weight=9];
206 -> 42[label="",style="solid", color="burlywood", weight=3];
171[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat (Succ wu200) (Succ wu210))",fontsize=16,color="black",shape="box"];171 -> 175[label="",style="solid", color="black", weight=3];
172[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat (Succ wu200) Zero)",fontsize=16,color="black",shape="box"];172 -> 176[label="",style="solid", color="black", weight=3];
173[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat Zero (Succ wu210))",fontsize=16,color="black",shape="box"];173 -> 177[label="",style="solid", color="black", weight=3];
174[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat Zero Zero)",fontsize=16,color="black",shape="box"];174 -> 178[label="",style="solid", color="black", weight=3];
39[label="deleteBy primEqChar (Char (Succ wu300)) (wu410 : wu411)",fontsize=16,color="black",shape="box"];39 -> 48[label="",style="solid", color="black", weight=3];
40[label="deleteBy primEqChar (Char (Succ wu300)) []",fontsize=16,color="black",shape="box"];40 -> 49[label="",style="solid", color="black", weight=3];
41[label="deleteBy primEqChar (Char Zero) (wu410 : wu411)",fontsize=16,color="black",shape="box"];41 -> 50[label="",style="solid", color="black", weight=3];
42[label="deleteBy primEqChar (Char Zero) []",fontsize=16,color="black",shape="box"];42 -> 51[label="",style="solid", color="black", weight=3];
175 -> 133[label="",style="dashed", color="red", weight=0];
175[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) (primEqNat wu200 wu210)",fontsize=16,color="magenta"];175 -> 179[label="",style="dashed", color="magenta", weight=3];
175 -> 180[label="",style="dashed", color="magenta", weight=3];
176[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) False",fontsize=16,color="black",shape="triangle"];176 -> 181[label="",style="solid", color="black", weight=3];
177 -> 176[label="",style="dashed", color="red", weight=0];
177[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) False",fontsize=16,color="magenta"];178[label="deleteBy0 wu17 (Char (Succ wu18)) primEqChar (Char (Succ wu19)) True",fontsize=16,color="black",shape="box"];178 -> 182[label="",style="solid", color="black", weight=3];
48 -> 10[label="",style="dashed", color="red", weight=0];
48[label="deleteBy0 wu411 wu410 primEqChar (Char (Succ wu300)) (primEqChar (Char (Succ wu300)) wu410)",fontsize=16,color="magenta"];48 -> 58[label="",style="dashed", color="magenta", weight=3];
48 -> 59[label="",style="dashed", color="magenta", weight=3];
48 -> 60[label="",style="dashed", color="magenta", weight=3];
49[label="[]",fontsize=16,color="green",shape="box"];50 -> 10[label="",style="dashed", color="red", weight=0];
50[label="deleteBy0 wu411 wu410 primEqChar (Char Zero) (primEqChar (Char Zero) wu410)",fontsize=16,color="magenta"];50 -> 61[label="",style="dashed", color="magenta", weight=3];
50 -> 62[label="",style="dashed", color="magenta", weight=3];
50 -> 63[label="",style="dashed", color="magenta", weight=3];
51[label="[]",fontsize=16,color="green",shape="box"];179[label="wu210",fontsize=16,color="green",shape="box"];180[label="wu200",fontsize=16,color="green",shape="box"];181[label="Char (Succ wu18) : deleteBy primEqChar (Char (Succ wu19)) wu17",fontsize=16,color="green",shape="box"];181 -> 183[label="",style="dashed", color="green", weight=3];
182[label="wu17",fontsize=16,color="green",shape="box"];58[label="Char (Succ wu300)",fontsize=16,color="green",shape="box"];59[label="wu411",fontsize=16,color="green",shape="box"];60[label="wu410",fontsize=16,color="green",shape="box"];61[label="Char Zero",fontsize=16,color="green",shape="box"];62[label="wu411",fontsize=16,color="green",shape="box"];63[label="wu410",fontsize=16,color="green",shape="box"];183 -> 33[label="",style="dashed", color="red", weight=0];
183[label="deleteBy primEqChar (Char (Succ wu19)) wu17",fontsize=16,color="magenta"];183 -> 184[label="",style="dashed", color="magenta", weight=3];
183 -> 185[label="",style="dashed", color="magenta", weight=3];
184[label="wu19",fontsize=16,color="green",shape="box"];185[label="wu17",fontsize=16,color="green",shape="box"];}

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

        ↳ HASKELL

          ↳ COR

            ↳ HASKELL

              ↳ Narrow

                ↳ QDP

                  ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

new_deleteBy0(wu17, wu18, wu19, Zero, Succ(wu210)) → new_deleteBy00(wu17, wu18, wu19)
new_deleteBy(wu300, :(wu410, wu411)) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
new_deleteBy01(:(wu410, wu411), Char(Zero), Char(Succ(wu300))) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Succ(wu210)) → new_deleteBy0(wu17, wu18, wu19, wu200, wu210)
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Zero) → new_deleteBy(wu19, wu17)
new_deleteBy00(wu17, wu18, wu19) → new_deleteBy(wu19, wu17)
new_deleteBy01(wu41, Char(Succ(wu4000)), Char(Succ(wu300))) → new_deleteBy0(wu41, wu4000, wu300, wu300, wu4000)
new_deleteBy01(:(wu410, wu411), Char(Succ(wu4000)), Char(Zero)) → new_deleteBy01(wu411, wu410, Char(Zero))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 2 SCCs.

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

        ↳ HASKELL

          ↳ COR

            ↳ HASKELL

              ↳ Narrow

                ↳ QDP

                  ↳ DependencyGraphProof

                    ↳ AND

                      ↳ QDP

                        ↳ QDPSizeChangeProof

                      ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_deleteBy01(:(wu410, wu411), Char(Succ(wu4000)), Char(Zero)) → new_deleteBy01(wu411, wu410, Char(Zero))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

new_deleteBy01(:(wu410, wu411), Char(Succ(wu4000)), Char(Zero)) → new_deleteBy01(wu411, wu410, Char(Zero))
The graph contains the following edges 1 > 1, 1 > 2, 3 >= 3

↳ HASKELL

  ↳ IFR

    ↳ HASKELL

      ↳ BR

        ↳ HASKELL

          ↳ COR

            ↳ HASKELL

              ↳ Narrow

                ↳ QDP

                  ↳ DependencyGraphProof

                    ↳ AND

                      ↳ QDP

                      ↳ QDP

                        ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_deleteBy(wu300, :(wu410, wu411)) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
new_deleteBy0(wu17, wu18, wu19, Zero, Succ(wu210)) → new_deleteBy00(wu17, wu18, wu19)
new_deleteBy01(:(wu410, wu411), Char(Zero), Char(Succ(wu300))) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Succ(wu210)) → new_deleteBy0(wu17, wu18, wu19, wu200, wu210)
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Zero) → new_deleteBy(wu19, wu17)
new_deleteBy00(wu17, wu18, wu19) → new_deleteBy(wu19, wu17)
new_deleteBy01(wu41, Char(Succ(wu4000)), Char(Succ(wu300))) → new_deleteBy0(wu41, wu4000, wu300, wu300, wu4000)

From the DPs we obtained the following set of size-change graphs:

new_deleteBy01(:(wu410, wu411), Char(Zero), Char(Succ(wu300))) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
The graph contains the following edges 1 > 1, 1 > 2, 3 >= 3
new_deleteBy01(wu41, Char(Succ(wu4000)), Char(Succ(wu300))) → new_deleteBy0(wu41, wu4000, wu300, wu300, wu4000)
The graph contains the following edges 1 >= 1, 2 > 2, 3 > 3, 3 > 4, 2 > 5
new_deleteBy(wu300, :(wu410, wu411)) → new_deleteBy01(wu411, wu410, Char(Succ(wu300)))
The graph contains the following edges 2 > 1, 2 > 2
new_deleteBy00(wu17, wu18, wu19) → new_deleteBy(wu19, wu17)
The graph contains the following edges 3 >= 1, 1 >= 2
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Succ(wu210)) → new_deleteBy0(wu17, wu18, wu19, wu200, wu210)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 5 > 5
new_deleteBy0(wu17, wu18, wu19, Zero, Succ(wu210)) → new_deleteBy00(wu17, wu18, wu19)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3
new_deleteBy0(wu17, wu18, wu19, Succ(wu200), Zero) → new_deleteBy(wu19, wu17)
The graph contains the following edges 3 >= 1, 1 >= 2

deleteBy0	ys y eq x True	= ys
deleteBy0	ys y eq x False	= y : deleteBy eq x ys